// map.cpp
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include "standard.hpp"
#include <cstdio>
#include <cstring>
#include <cstdio>
#include "util/mem.hpp"
#include "util/equality.hpp"
#include "util/hash.hpp"

namespace Ripe {

template <class K, class V>
Map<K,V>::Map(uint32_t n)
{
  alloc_size = map_prime(2*n);
  data = allocate(alloc_size);
  size = 0;
}

template <class K, class V>
Map<K,V>::~Map()
{
  if (data != NULL)
    mem_free(data);
}

template <class K, class V>
bool Map<K,V>::get(K key, V* value)
{
  assert(data != NULL);
  uint32_t hash_value = generic_hash<K>(key) % alloc_size;
  for (uint32_t i = 0; i < alloc_size; i++){
    // Quadratic probing
    uint32_t loc = (hash_value + i*i) % alloc_size;

    if (data[loc].type == BucketEmpty) {
      return false;
    } else if (data[loc].type == BucketFull and generic_equal<K>(data[loc].key,
                key)){
      *value = data[loc].value;
      return true;
    }
  }
  return false;
}

template <class K, class V>
V Map<K,V>::get(K key) throw(ErrorKey)
{
  assert(data != NULL);
  V value;
  if (not get(key, &value)) {
    throw ErrorKey();
  }
  return value;  
}

template <class K, class V>
bool Map<K,V>::set(K key, V value)
{
  assert(data != NULL);

  if (size + 1 > alloc_size / 2){
    // Hash table is now more than 50% full. Rehash.
    uint32_t new_size = map_prime(alloc_size + 1);

    // Get new buckets.
    Bucket<K,V>* data_new = allocate(new_size);

    // Hash into the new buckets.
    for (uint32_t i = 0; i < alloc_size; i++){
      if (data[i].type == BucketFull){
        set2(data_new, new_size, data[i].key, data[i].value);
      }
    }
    // Replace the buckets.
    alloc_size = new_size;
    mem_free(data);
    data = data_new;
  }
  bool found = set2(data, alloc_size, key, value);
  if (not found) size++;
  return found;
}

template <class K, class V>
bool Map<K,V>::set2(Bucket<K,V>* buckets, uint32_t n, K key, V value)
{
  uint32_t hash_value = generic_hash<K>(key) % n;
  // Empty is initialized so that a warning would be cleared. It is the number
  // of the first lazy bucket that we run into. It is only valid if
  // found_empty == true.
  uint32_t empty = 0; bool found_empty = false;

  for (uint32_t i = 0; i < n; i++){
    // Quadratic probing
    uint32_t loc = (hash_value + i*i) % n;

    if (buckets[loc].type == BucketLazy) {
      // Find first empty lazy spot.
      if (not found_empty) {
        empty = loc;
        found_empty = true;
      }
    } else if (buckets[loc].type == BucketEmpty) {
      // Found an empty bucket. If we found a lazy spot before, fill it up now.
      if (found_empty) loc = empty;
      buckets[loc].key = key;
      buckets[loc].value = value;
      buckets[loc].type = BucketFull;
      return false;
    } else if (generic_equal<K>(buckets[loc].key, key)){
      // Found the key, update it.
      buckets[loc].value = value;
      return true;
    }
  }

  // If none of the buckets visited were empty, at least one must have been
  // lazy.
  if (found_empty){
    buckets[empty].key = key;
    buckets[empty].value = value;
    buckets[empty].type = BucketFull;
    return false;
  }

  // Should never reach this point, report an error.
  assert_never();
  return false;
}

template <class K, class V>
Bucket<K,V>* Map<K,V>::allocate(uint32_t n)
{
    // Get new buckets.
    Bucket<K,V>* data_new = (Bucket<K,V>*) mem_malloc(sizeof(Bucket<K,V>) 
                                                       * n);
    for (uint32_t i = 0; i < n; i++){
      data_new[i].type = BucketEmpty;
    }
    return data_new;
}


template <class K, class V>
void Map<K,V>::print()
{
  std::printf("[");
  for (uint32_t i = 0; i < alloc_size; i++){
    switch(data[i].type){
      case BucketFull:
        std::printf("*");
        break;
      case BucketEmpty:
        std::printf(" ");
        break;
      case BucketLazy:
        std::printf(".");
        break;
    }
  }
  std::printf("] %d in %d buckets\n", size, alloc_size);
}

template <class K, class V>
MapIterator<K,V>::MapIterator(Map<K,V>* m)
{
  reset(m);
}

template <class K, class V>
MapIterator<K,V>::MapIterator()
{
  more = false;
  idx = 0;
}

template <class K, class V>
void MapIterator<K,V>::reset(Map<K,V>* m)
{
  more = false;
  idx = 0;
  map = m;
  find_next();
}

template <class K, class V>
void MapIterator<K,V>::find_next()
{
  more = false;
  for (;idx < map->alloc_size; idx++) {
    if (map->data[idx].type == BucketFull) {
      more = true;
      break;
    }  
  }
}

template <class K, class V>
bool MapIterator<K,V>::has_more()
{
  return more;
}

template <class K, class V>
void MapIterator<K,V>::get(K* one, V* two)
{
  if (not more){
    throw ErrorIterator();
  }
  *one = map->data[idx].key;
  *two = map->data[idx].value;
  idx++;
  find_next();
}    

}
